#include "KDtree.h"
#include <algorithm>

KDtree::KDtree(const std::vector<Point2D>& i_vector)
{
	auto comparator_x =[](const Point2D& i_p1, const Point2D& i_p2) -> int
	{
		if(i_p1.x == i_p2.x)
			return 0;
		else
		{
			if(i_p1.x > i_p2.x)
				return 1;
			else
				return 0;
		}
	};
	auto comparator_y=[](const Point2D& i_p1, const Point2D& i_p2) -> int
	{
		if(i_p1.y== i_p2.y)
			return 0;
		else
		{
			if(i_p1.y> i_p2.y)
				return 1;
			else
				return 0;
		}
	};
	std::vector<Point2D> sorted_x=i_vector;
	std::vector<Point2D> sorted_y=i_vector;
	std::sort(sorted_y.begin(), sorted_y.end(), comparator_y);
	std::sort(sorted_x.begin(), sorted_x.end(), comparator_x);
	if(sorted_x[sorted_x.size()-1].x - sorted_x[0].x >= sorted_y[sorted_y.size()-1].y - sorted_y[0].y)
		p_CreateTree(mp_root, sorted_x, sorted_y, 0, sorted_x.size()-1, 0); 
	else
		p_CreateTree(mp_root, sorted_y, sorted_x, 0, sorted_x.size()-1, 1);
};


void KDtree::p_CreateTree(Node* i_node, std::vector<Point2D>& i_first, 
			std::vector<Point2D>& i_second, int i_lb, int i_rb, int i_count)
{
	i_node=new Node();
	if(i_lb==i_rb)
	{
		i_node->mp_point=i_first[i_lb];
		return;
	}
	if(i_count % 2 == 0)
	{
		i_node->m_ifasix_x=true;
		i_node->value=i_first[(i_lb + i_rb) / 2].x;
	}
	else
	{
		i_node->m_ifasix_x=false;
		i_node->value=i_first[(i_lb + i_rb) / 2].y;
	}
	for(int i=i_lb; i<=(i_lb + i_rb) / 2; i++)
		i_first[i].id=0;
	for(int i=(i_lb + i_rb) / 2+1;i<=i_rb; i++)
		i_first[i].id=1;
	int left_ind=i_lb;
	int right_ind=(i_lb+i_rb)/2 +1;
	Point2D * temp= new Point2D[i_rb-i_lb+1];
	for(int j=i_lb; j<=i_rb; j++)
	{
		if(i_second[j].id==0)
			temp[left_ind++]=i_second[j];
		else
			temp[right_ind++]=i_second[j];
	}
	for(int j=i_lb; j<=i_rb; j++)
		i_second[j]=temp[j];
	delete[] temp;
	p_CreateTree(mp_root->left, i_second, i_first, i_lb, (i_rb-i_lb)/2, i_count+1);
	p_CreateTree(mp_root->right, i_second, i_first, (i_rb-i_lb)/2+1, i_rb, i_count+1);
};
 